package com.example.demo.leetcode.zuocheng.graph;

import java.util.*;

/**
 *
 * 给定一个图,求最小生成树
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/4 12:29
 */
public class 最小生成树_Kruskal {




    public static List<Edge> kruskal(int [][] arr){

        HashMap<String,Node> map = new HashMap<>();

        //将最小生成树转换成基础结构
        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        for(int i =0 ;i<arr.length;i++){

            int [] temp=arr[i];

            Node from = map.get(temp[1]+"") == null ?  new Node(temp[1]+"") : map.get(temp[1]+"");
            Node to = map.get(temp[2]+"") == null ?  new Node(temp[2]+"") : map.get(temp[2]+"");
            from.out++;
            to.in++;

            Edge edge = new Edge(temp[0],from,to);

            from.edges.add(edge);
            from.nexsts.add(to);

            queue.add(edge);
            map.put(from.value,from);
            map.put(to.value,to);
        }

        HashMap<String,Node> kruMap = new HashMap<>();
        List<Edge> resultList = new ArrayList<>();
        // 采用交并集
        while(!queue.isEmpty()){
            Edge edge = queue.poll();
            //edge
            boolean flag =false;
            Node from = new Node(edge.from.value);
            Node to = new Node(edge.to.value);

            //两个节点都存在 判断是否不可达
             if(kruMap.containsKey(edge.from.value) && kruMap.containsKey(edge.to.value)){
                from = kruMap.get(edge.from.value);
                //bfs遍历,整个map中是否有某个点可以到达to
                if(!bfsKruMap(kruMap,to)){
                    from.out++;
                    Edge edge2 = new Edge(edge.weight,from,to);
                    from.edges.add(edge2);
                    from.nexsts.add(to);
                    kruMap.get(edge.to.value).in++;
                    flag = true;
                }
            }
            //krumap中不存在 from节点，直接存入from 加入结果集合
            if(!kruMap.containsKey(edge.from.value)){
                //构造新的节点存入KruMap
                from.out++;
                Edge edge2 = new Edge(edge.weight,from,to);
                from.edges.add(edge2);
                from.nexsts.add(to);
                kruMap.put(edge.from.value,from);
                flag = true;
            }
            //krumap不存在 to节点,直接加入集合
            if(!kruMap.containsKey(edge.to.value)){
                to.in++;
                kruMap.put(edge.to.value,to);
                flag = true;
            }

            //有新的节点，为true，有一个节点不是新的，另一个节点不可达，是新的
            if(flag){
                resultList.add(new Edge(edge.weight,from,to));
            }
        }
        return resultList;
    }


    public static boolean bfsKruMap(HashMap<String,Node> map,Node to){

        for(Map.Entry<String,Node> entry : map.entrySet()){
            Node value = entry.getValue();
            LinkedList<Node> queue = new LinkedList<>();
            queue.add(value);
            while(!queue.isEmpty()){
                Node poll = queue.poll();
                if(poll.value.equals(to.value)){
                    return true;
                }
                for(Node temp: poll.nexsts){
                    queue.add(temp);
                }
            }
        }

        return false;
    }


    public static void main(String[] args) {
        int [][] arr ={{10,1,2},{11,2,3},{12,3,4},{14,4,1},{15,2,1}};
        List<Edge> kruskal = kruskal(arr);
        for(Edge edge : kruskal){
            System.out.println(edge.weight + ":"+edge.from.value+":"+edge.to.value);
        }
    }


}
